//V& operator[](const K& key) {
//	pair<iterator, bool> p = insert(make_pair(key, V()));
//	return ret.first->second;
//}

//class Solution {
//public:
//    vector<int> postorderTraversal(TreeNode* root) {
//        vector<int> v;
//        stack<TreeNode*> s;
//        if (root == nullptr) {
//            return v;
//        }
//        TreeNode* _root = root;
//        TreeNode* last = nullptr;
//        int x = 1;
//        while (!s.empty() || x) {
//            x = 0;
//            while (_root) {
//                s.push(_root);
//                _root = _root->left;
//            }
//            if (s.top()->right == nullptr) {
//                v.push_back(s.top()->val);
//                last = s.top();
//                s.pop();
//                while (!s.empty() && s.top()->right == last) {
//                    v.push_back(s.top()->val);
//                    last = s.top();
//                    s.pop();
//                }
//            }
//            if (!s.empty())
//                _root = s.top()->right;
//        }
//        return v;
//    }
//};

//#include <iostream>
//#include <string>
//using namespace std;
//
//int main() {
//    string s;
//    string str("-1");
//    getline(cin, s);
//    for (int i = 0; i < s.size(); i++) {
//        size_t pos = s.find(s[i]);
//        size_t rpos = s.rfind(s[i]);
//        if (pos == rpos) {
//            str.clear();
//            str.push_back(s[i]);
//            break;
//        }
//    }
//    cout << str << endl;
//    return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//int MaxCount(int x, int y) {
//    while (y) {
//        int r = x % y;
//        x = y;
//        y = r;
//    }
//    return x;
//}
//int main() {
//    int n = 0, a = 0;
//    cin >> n >> a;
//    vector<int> v;
//    for (int j = 0; j < n; j++) {
//        vector<int> v1;
//        for (int i = 0; i < n; i++) {
//            v1.resize(n);
//            cin >> v1[i];
//            if (a >= v1[i]) {
//                a += v1[i];
//            }
//            else {
//                a += MaxCount(v1[i], a);
//            }
//        }
//        v.push_back(a);
//    }
//    for (int i = 0; i < n; i++) {
//        cout << v[i] << endl;
//    }
//    return 0;
//}

//#include <iostream>
//#include <vector>
//using namespace std;
//int MaxCount(int x, int y) {
//    while (y) {
//        int r = x % y;
//        x = y;
//        y = r;
//    }
//    return x;
//}
//int main() {
//    int n = 0, a = 0;
//    while (cin >> n >> a) {
//        for (int i = 0; i < n; i++) {
//            int d = 0;
//            cin >> d;
//            if (d <= a) {
//                a += d;
//            }
//            else {
//                a += MaxCount(d, a);
//            }
//        }
//        cout << a << endl;
//    }
//    return 0;
//}

//#include <iostream>
//#include <string>
//#include <algorithm>
//using namespace std;
//int main() {
//    string str1;
//    string str2;
//    while (cin >> str1 >> str2) {
//        int count = 0;
//        if (str1.size() == str2.size()) {
//            int length = str1.size();
//            for (int i = 0; i < length; i++) {
//                if (str1[i] != str2[i]) {
//                    count++;
//                }
//            }
//        }
//        else {
//            stable_sort(str1.begin(), str1.end());
//            stable_sort(str2.begin(), str2.end());
//            int i = 0, j = 0, same = 0;
//            while (i < str1.size() && j < str2.size()) {
//                if (str1[i] < str2[j]) {
//                    i++;
//                }
//                else if (str1[i] > str2[j]) {
//                    j++;
//                }
//                else {
//                    same++;
//                    i++;
//                    j++;
//                }
//            }
//            int max = str1.size() > str2.size() ? str1.size() : str2.size();
//            int min = str1.size() < str2.size() ? str1.size() : str2.size();
//            count += min - same;
//            count += max - min;
//        }
//        cout << count << endl;
//    }
//    return 0;
//}

//class Bonus {
//public:
//    int getMost(vector<vector<int> > board) {
//        int Max = 0;
//        int length = board.size();
//        int wide = board[0].size();
//        int i = 0, j = 0;
//        while (i < length) {
//            while (j < wide) {
//                if (i == length - 1) {
//                    Max += board[i][j++];
//                }
//                else if (j == wide - 1) {
//                    Max += board[i++][j];
//                }
//                else {
//                    if (board[i + 1][j] > board[i][j + 1]) {
//                        Max += board[i++][j];
//                    }
//                    else {
//                        Max += board[i][j++];
//                    }
//                }
//                if (i == length - 1 && j == length - 1) {
//                    return Max;
//                }
//            }
//        }
//        return Max;
//    }
//};

